package com.practice.niuke.new_direct_basics.class05;

/**
 * 如何判断一颗二叉树是否是满二叉树？
 *
 * @author lineng
 * @create 2020-02-13 16:52
 */
public class IsFull {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    /**
     * 判断一颗二叉树是否是满二叉树时，
     * 递归函数作用于每个节点返回的统一信息：
     * <f>
     * （1）int nodes: 整棵子树的节点个数
     * （2）int height: 整棵子树的高度
     */
    public static class Info {
        public int nodes;
        public int height;

        public Info(int nodes, int height) {
            this.nodes = nodes;
            this.height = height;
        }
    }

    /**
     * 递归函数：以x为头的树，返回Info1（2个信息）
     *
     * @param x 节点
     * @return Info
     */
    public static Info process(Node x) {
        if (x == null) {
            return new Info(0, 0);
        }
        // x节点的左子树（不包括x节点）返回的两个信息
        Info leftInfo = process(x.left);
        // x节点的右子树（不包括x节点）返回的两个信息
        Info rightInfo = process(x.right);

        // 以x节点为头的子树的节点个数：
        // x节点的左子树（不包括x节点）的节点个数 + x节点的右子树（不包括x节点）的节点个数 + 1（自己）
        int nodes = leftInfo.nodes + rightInfo.nodes + 1;
        // 以x节点为头的子树的高度：
        // x节点的左子树（不包括x节点）的高度 和 x节点的右子树（不包括x节点）的高度 的最大值 + 1（自己在子树的上一层）
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;

        return new Info(nodes, height);
    }

    /**
     * 判断一颗二叉树是否是满二叉树
     * (里面调用递归流程)
     *
     * @return boolean
     */
    public static boolean isFull(Node head){
        Info info = process(head);
        int N = info.nodes;
        int H = info.height;
        // 判断N是否等于2^H -1
        return N == (1<<H)-1;
    }
}
